/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function (s) {
  let res = []
  let path = []
  let n = s.length

  //isPalindrome[i][j]用于判断s[i]~s[j]是否为回文串
  const isPalindrome = Array.from({ length: n }, () => new Array(n).fill(false))
  for (let right = 0; right < n; right++) {
    for (let left = 0; left <= right; left++) {
      if (s[left] === s[right] && ((right - left <= 2) || isPalindrome[left + 1][right - 1])) {
        isPalindrome[left][right] = true
      }
    }
  }

  // 回溯函数
  function backTrack(start) {
    if (start === n) {
      res.push([...path])
      return
    }

    for (let end = start; end < n; end++) {
      if (isPalindrome[start][end]) {
        path.push(s.substring(start, end + 1))
        backTrack(end + 1)
        path.pop()
      }
    }
  }
  //回溯函数：从索引0开始分隔回文串
  backTrack(0)

  //返回结果数组
  return res

};